# Powered by Python 2.7

# To cancel the modifications performed by the script
# on the current graph, click on the undo button.

# Some useful keyboards shortcuts : 
#   * Ctrl + D : comment selected lines.
#   * Ctrl + Shift + D  : uncomment selected lines.
#   * Ctrl + Space  : run script.
#   * Ctrl + F  : find selected text.
#   * Ctrl + R  : replace selected text.

from tulip import *


def makeTreeA(graph,viewColor, viewLabel):
	
	tree1 = tlp.newSubGraph(graph, "firstTree");
	Nroot = tree1.addNode();
	#viewColor.setNodeValue(Nroot, tlp.Color(0,0,255));
	#viewLabel.setNodeValue(Nroot, "b");
	N1 = tree1.addNode();
	N2 = tree1.addNode();
	N3 = tree1.addNode();
	N4 = tree1.addNode();
	N5 = tree1.addNode();
	N21 = tree1.addNode();
	N31 = tree1.addNode();
	
	tree1.addEdge(Nroot, N1);
	tree1.addEdge(Nroot, N2);
	tree1.addEdge(Nroot, N3);
	tree1.addEdge(Nroot, N4);
	tree1.addEdge(Nroot, N5);
	tree1.addEdge(N2, N21);
	tree1.addEdge(N3, N31);
	
	return tree1;

def makeTreeB(graph, viewColor, viewLabel):
	
	tree2 = tlp.newSubGraph(graph, "secondTree");
	Nroot = tree2.addNode();
	#viewColor.setNodeValue(Nroot, tlp.Color(0,0,255));
	#viewLabel.setNodeValue(Nroot, "b");
	N1 = tree2.addNode();
	N2 = tree2.addNode();
	N3 = tree2.addNode();
	
	N21 = tree2.addNode();
	N31 = tree2.addNode();
	N32 = tree2.addNode();
	N33 = tree2.addNode();
	N321 = tree2.addNode();
		
	tree2.addEdge(Nroot, N1);
	tree2.addEdge(Nroot, N2);
	tree2.addEdge(Nroot, N3);
	tree2.addEdge(N2, N21);
	tree2.addEdge(N3, N31);
	tree2.addEdge(N3, N32);
	tree2.addEdge(N3, N33);
	tree2.addEdge(N33, N321);
	
	return tree2;

def DF(T) :
	if (T.numberOfEdges == 0) :
		DF = 0;
	else :
		DF = 0;
		for i in T.getSubGraphs():
			DF += DT(T.getSubGraph(i));
	return DF;

def DT(T) :
#T -> arbre dont la sous foret est F;
	if (T.numberOfNodes == 0) :
		return 0;
	else :
		return  DF(T) + COST_INSER_DEL;
			# cout de deletion/insertion = 1;

def mGMM(T1, T2, i, j , graph) :
	tmpGraph = tlp.newSubGraph(graph, "tmpGraph");
	Ns = tmpGraph.addNode();
	Nt = tmpGraph.addNode();
	Nei = tmpGraph.addNode();
	Nej = tmpGraph.addNode();
	
	for k in T1.getSubGraph(i).getSubGraphs() :
		Nk = tmpGraph.addNode();
		
		Esk = tmpGraph.addEdge(Ns, Nk);
		viewDouble.setEdgeValue(Esk, 0);
		viewInteger.setEdgeValue(Esk, 1);
		
		Esei = tmpGraph.addEdge(Ns, Nei);
		viewDouble.setEdgeValue(Esei, 0);
		viewInteger.setEdgeValue(Esei, l);
		
		Eejt = tmpGraph.addEdge(Nej, Nt);
		viewDouble.setEdgeValue(Eejt, 0);
		viewInteger.setEdgeValue(Eejt, k);
		
		Eeiej = tmpGraph.addEdge(Nei, Nej);
		viewDouble.setEdgeValue(Eeiej, 0);
		viewInteger.setEdgeValue(Eeiej, max(k, l) - min (k, l));
		
		for l in T2.getSubGraph(j).getSubGraphs() :
			Nl = tmpGraph.addNode();
			Ekl = tmpGraph.addEdge(Nk, Nl);
			viewDouble.setEdgeValue(Ekl, DTT(T1.getSubGraph(i).getSubGraph(k), T2.getSubGraph(j).getSubGraph(l)));
			viewInteger.setEdgeValue(Ekl, 1);
		
			Eeil = tmpGraph.addEdge(Nei, Nl);
			viewDouble.setEdgeValue(Eeil, DT(T2.getSubGraph(j).getSubGraph(l)));
			viewInteger.setEdgeValue(Eeil, 1);
			
			Ekej = tmpGraph.addEdge(Nk, Nej);
			viewDouble.setEdgeValue(Ekej, DT(T1.getSubGraph(i).getSubGraph(k)));
			viewInteger.setEdgeValue(Ekej, 1);
			
			Elt = tmpGraph.addEdge(Nl, Nt);
			viewDouble.setEdgeValue(Elt, 0);
			viewInteger.setEdgeValue(Elt, 1);
		
		
		return 1;	
		

def DFF(T1, T2, i, j, DF1, DF2, graph) :
	
	listMin1 = [];
	listMin2 = [];
	
	for t in T2.getSubGraph(j).getSubGraphs() :
		DF2t = DF(T2.getSubGraph(j));
		listMin1.append(DFF(T1, T2.getSubGraph(j), i, t, DF1, DF2t, graph) - DF2t);
		listMin1.sort();
	DFF1 = DF2 + listMin1[0];
	
	for s in T1.getSubGraph(i).getSubGraphs() :
		DF1s = DF(T1.getSubGraph(i));
		listMin2.append(DFF(T1.getSubGraph(i), T2, s, j, DF1s, DF2, graph) - DF1s);
		listMin2.sort();
	DFF2 = DF1 + listMin2[0];
	
	
	# min gamma (MM(i,j));
	DFF3 = mGMM(T1, T2, i, j, graph);
	
	return min(DFF1, DFF2, DFF3);
	
def DTT(T1, T2, i, j, DFF, DT1, DT2, graph) :
	
	listMin1 = [];
	listMin2 = [];
	
	print "testDTT1";
	
	for t in T2.getSubGraph(j).getSubGraphs() :
		DT2t = DT(T2.getSubGraph(j));
		listMin1.append(DTT(T1, T2.getSubGraph(j), i, t, DFF(T1, T2.getSubGraph(j), i, t,  DF(T1), DF(T2.getSubGraph(j)), graph), DT1, DT2t ));
		listMin1.sort();
	DTT1 = DT2 + listMin1[0];
	
	for s in T1.getSubGraph(i).getSubGraphs() :
		DT1s = DT(T1.getSubGraph(i));
		listMin2.append(DTT(T1.getSubGraph(i), T2, s, j, DFF(T1.getSubGraph(i), T2, s, j, DF(T1.getSubGraph(i), DF(T2)), graph), DT1s, DT2));
		listMin2.sort();
	DTT2 = DT1 + listMin2[0];
		
	DTT3 = DFF + COST_SUB;
	
	
	print "testDTT2";
	
	return min(DTT1, DTT2, DTT3);

def DGeneral(T1, T2, graph) :
	
	listeDTT = [[]for i in T1.getSubGraphs()]; 
	print(T1); 
	print(T2); 
	tmp = T1.getSubGraphs();
	print(T1.getSubGraph(tmp));
	listeDF1 = [];
	listeDT1 = [];
	for i in T1.getSubGraphs() :
		DF1 = DF(T1.getSubGraph(i));
		listeDF1.append(DF1);
		#DT1 = DT(T1.getSubGraph(i));
		DT1 = DF1 + 1;
		listeDT1.append(DT1);
	
	#print listeDF1;
	#print listeDT1;
	print "test";
	listeDF2 = [];
	listeDT2 = [];
	for i in T2.getSubGraphs() :
		DF2 = DF(T2.getSubGraph(i));
		listeDF2 .append(DF2);
		DT2 = DF2 + 1;
		listeDT2.append(DT2);
	
	for i in T1.getSubGraphs() :
		for j in T2.getSubGraphs() :
			DF1F2 = DFF(T1, T2, i, j ,listeDF1[i] ,listeDF2[j] , graph);
			DT1T2 = DTT(T1, T2, i, j, DF1F2, listeDT1[i], listeDT2[j], graph);
			listeDTT[i].append(DT1T2);
	
	return listeDTT;
	

#def Distance(T1, T2):
#	if (T1.numberOfNodes() == 0) and (T2.numberOfNodes() == 0):
#		return 0;
#	if (T2.numberOfNodes() == 0):
#		DF1O = 0;
#		for i in T1.getNodes():
#			for j in i.getNodes():
#				DF1O += Distance( j , T2);
	
#def comparaison(T1, T2):
#	theta = newGraph();
#	for i in T1.getNodes():
#		# calcul du determinant D(Fi[i],theta)
#		DF1 = 0;
#		for k in  i.getNodes();
#			DF1 += Distance(k, theta) + gamma();
#	for j in T2.getNodes():
#		
#	

def initLayout(viewLayout) :
	dataSet = tlp.getDefaultPluginParameters("Tree Leaf", graph)
	dataSet["3D layout"] = False;
	graph.computeLayoutProperty("Tree Leaf", viewLayout, dataSet);
	viewLayout.scale(tlp.Coord(.5,.5,.5));
	
def main(graph) : 
	global COST_SUB;
	COST_SUB = 1;
	global COST_INSER_DEL;
	COST_INSER_DEL = 1;
	graph.clear();
	viewColor =  graph.getColorProperty("viewColor");
	viewLabel =  graph.getStringProperty("viewLabel");
	viewLayout =  graph.getLayoutProperty("viewLayout");
	global viewDouble;
	viewDouble =  graph.getDoubleProperty("viewDouble");
	global viewInteger;
	viewInteger =  graph.getIntegerProperty("viewInteger");
	#makeTree(graph, viewLayout);
	tree1 = makeTreeA(graph, viewColor, viewLabel);
	tree2 = makeTreeB(graph, viewColor, viewLabel);
	
	map = DGeneral(tree1, tree2, graph);
	
	print(tree1); 
	print(map);
	
	initLayout(viewLayout);
	
	return True;